unit Common.List;

interface

uses System.SysUtils, System.Classes;

type
    PPointerItem = ^TPointerItem;

    TPointerItem = record
    public
        Data: Pointer;
        Next: PPointerItem;
        Prev: PPointerItem;
    end;

    TLinkedListBase = class
    private
        First: PPointerItem;
        Last: PPointerItem;
        FreedList: TList;
        nCount: integer;
    protected
        procedure Append(Data: Pointer); virtual;
        function RemoveFirst(): Pointer; virtual;
        function RemoveLast(): Pointer; virtual;
        property Count: integer read nCount;
    public
        procedure Clear();
        function IsEmpty(): Boolean;
        constructor Create();
        destructor Destroy(); override;
    end;

    TLinkedList = class(TLinkedListBase)
    public
        function RemoveFirst(): Pointer; override;
        function RemoveLast(): Pointer; override;
        procedure Append(Data: Pointer); override;
        property Count;
    end;

    TStack<T> = class(TLinkedListBase)
    public
        procedure Push(Data: T);
        function Pop(): T;
        property Count;
    end;

implementation

{ TLinkedList }

procedure TLinkedListBase.Append(Data: Pointer);
var
    rec: PPointerItem;
begin
    rec := nil;
    TMonitor.Enter(FreedList);
    try
        if FreedList.Count > 0 then
        begin
            rec := FreedList.Items[FreedList.Count - 1];
            FreedList.Delete(FreedList.Count - 1);
        end;

        if not assigned(rec) then
        begin
            System.GetMem(rec, Sizeof(TPointerItem));
        end;

        if assigned(Last) then
        begin
            Last^.Next := rec;
        end;

        rec^.Data := Data;
        rec^.Next := nil;
        rec^.Prev := Last;
        Last := rec;

        if not assigned(First) then
        begin
            First := rec;
        end;

        inc(nCount);

    finally
        TMonitor.Exit(FreedList);
    end;

end;

procedure TLinkedListBase.Clear;
var
    tmpFirst: PPointerItem;
begin
    TMonitor.Enter(FreedList);
    try
        while (First <> nil) do
        begin
            tmpFirst := First.Next;
            dispose(First);
            First := tmpFirst;
        end;
    finally
        nCount := 0;
        TMonitor.Exit(FreedList);
    end;
end;

constructor TLinkedListBase.Create;
begin
    inherited Create;
    nCount := 0;
    FreedList := TList.Create;
end;

destructor TLinkedListBase.Destroy;
begin
    Clear();
    FreedList.Free;
    inherited;
end;

function TLinkedListBase.IsEmpty: Boolean;
begin
    result := true;
    TMonitor.Enter(FreedList);
    try
        result := not assigned(First);
    finally
        TMonitor.Exit(FreedList);
    end;
end;

function TLinkedListBase.RemoveFirst: Pointer;
begin
    result := nil;
    TMonitor.Enter(FreedList);
    try
        if assigned(First) then
        begin
            FreedList.Add(First);
            result := First^.Data;
            First^.Data := nil;
            First := First^.Next;
            if (assigned(First)) then
            begin
                First^.Prev := nil;
            end
            else
            begin
                Last:=nil;
            end;
            dec(nCount);
        end;
    finally
        TMonitor.Exit(FreedList);
    end;
end;

function TLinkedListBase.RemoveLast: Pointer;
begin
    result := nil;
    TMonitor.Enter(FreedList);
    try
        if assigned(Last) then
        begin
            FreedList.Add(Last);
            result := Last^.Data;
            Last^.Data := nil;
            Last := Last^.Prev;
            dec(nCount);
        end;
    finally
        TMonitor.Exit(FreedList);
    end;
end;

{ TLinkedList<T> }

procedure TLinkedList.Append(Data: Pointer);
begin
    inherited Append(Data);
end;

function TLinkedList.RemoveFirst: Pointer;
begin
    result := inherited RemoveFirst();
end;

function TLinkedList.RemoveLast: Pointer;
begin
    result := inherited RemoveLast();
end;

{ TStack<T> }

function TStack<T>.Pop: T;
begin
    result := T(inherited RemoveLast()^);
end;

procedure TStack<T>.Push(Data: T);
begin
    inherited Append(@Data);
end;

end.
